package Algorithm;
/*
* 解决背包问题
*
* */
public class Bag {
    public static void main(String[] args) {
        int bag=4;
        int[] w = {1,4,3};
        int[] v = {1500,3000,2000};
        String[] name={"吉他","音响","电脑"};
        deal(w,v,name,bag);
    }
    // 使用动态规划解决
    public static void deal(int[] w,int[] v,String[] name,int bag){
        //step 1 创建二维数组 v[物品总个数][背包容量]
        int[][] vv =new int[name.length+1][bag+1];

        //step 2 初始化 第一行和第一列全为0
        for (int i = 0; i < vv.length; i++) {
            vv[i][0]=0;
        }
        for (int i = 0; i < vv[0].length; i++) {
            vv[0][i]=0;
        }

        //step 3 构建完善二维数组，获得最大背包价值
        for (int i = 1; i < vv.length ; i++) {
            for (int j = 1; j < vv[0].length; j++){
                // 当前背包容量为 j  当前物品重量 w[i]  当前物品价值v[i] vv[i][j] 当前背包容量的最大价值
                int weight = w[i-1];
                int value = v[i-1];
                // 情况一 当前物品重量大于背包容量
                if(weight>j){
                    vv[i][j] = vv[i-1][j];
                }
                // 情况二 当前物品重量小于等于背包重量
                if(weight<=j){
                    // 这里取 max{当前物品价值加剩余空间最大价值,上一行最大价值}
                    int max = value + vv[i-1][j-weight];
                    if(max>vv[i-1][j]) vv[i][j] =max;
                    else vv[i][j]=vv[i-1][j];
                }
            }
        }

        // 输出数组
        for (int i = 0; i < vv.length ; i++) {
            for (int j = 0; j < vv[0].length; j++){
                System.out.print(vv[i][j]+" ");
            }
            System.out.println();
        }


    }
}
